// 注：参考https://zhuanlan.zhihu.com/p/340950042
#include<iostream>
#include <queue>
#include <set>
#include <cmath>
#include <algorithm>
#include<stack>
using namespace std;
int n, m; // n为点数，m为边数
const int N = 1010;
const int INF = 0x7ffffff;
int g[N][N] = { 0 }; // 图，值代表边权

int etv[N] = { 0 };
int ltv[N] = { 0 };
int ete[N] = { 0 };
int lte[N] = { 0 };

int indegree[N] = { 0 };

stack<int> etvStack; // 拓扑序列

void criticalPath()
{
	// 计算入度
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (g[i][j] != INF)
			{
				indegree[j]++;
			}
		}
	}
	// 找出入度为零的点
	queue<int> q;
	for (int i = 0; i < n; i++)
	{
		if (indegree[i] == 0)
		{
			q.push(i);
		}
	}
	
	// 求拓扑序列
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		etvStack.push(v);
		// 遍历出度
		for (int i = 0; i < n; i++)
		{
			if (g[v][i] != INF)
			{
				indegree[i]--;
				if (indegree[i] == 0)
				{
					q.push(i);
				}
				// 计算事件最早开始时间
				if (etv[v] + g[v][i] > etv[i])
				{
					etv[i] = etv[v] + g[v][i];
				}
			}
		}
	}
	int endVertex = etvStack.top();// 最后一个点，即出度为0的点
	// 所有点（事件）的最迟开始时间为最后一个点（事件）的最早开始时间（即整个项目结束时间）
	for (int i = 0; i < n; i++)
	{
		ltv[i] = etv[endVertex];
	}
	// 求时间最迟开始时间（根据拓扑序列倒着求）
	while (!etvStack.empty())
	{
		int v = etvStack.top();
		etvStack.pop();

		for (int i = 0; i < n; i++)
		{
			if (g[v][i] != INF)
			{
				if (ltv[v] > ltv[i] - g[v][i])
				{
					ltv[v] = ltv[i] - g[v][i];
				}
			}
		}
	}

	// 求边（活动）的最早开始时间
	// 点（事件）的最早开始时间等于其出度边的最早开始时间
	int index = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			// 遍历每一条边, index代表边的编号
			if (g[i][j] != INF)
			{
				ete[index++] = etv[i];
			}
		}
	}

	// 求边（活动）的最迟开始时间
	// 点的最迟开始时间减去该点出度边的权值等于该出度边的最迟开始时间
	index = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			// 遍历每一条边, index代表边的编号
			if (g[i][j] != INF)
			{
				lte[index++] = ltv[j] - g[i][j];
			}
		}
	}

	// 最早开始和最迟开始时间相等的活动（边）即为关键路径
	for (int i = 0; i < m; i++)
	{
		if (lte[i] == ete[i])
		{
			// 关键路径
		}
	}
}

int main()
{

}